package offer.offer04;

/**
 * 100, 65, 五分钟一步到位……
 * 因为是二叉搜索树, p, q节点一定分布在该目标节点的两个子树上,(因为如果不在, 则可以再变深一层)
 * 因为是二傻搜索树, 所以应该是第一个位于两个目标值之间的节点
 */
public class Solution68 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        int max = Math.max(p.val, q.val);
        int min = Math.min(p.val, q.val);
        int cur = root.val;
        if(cur > max)
            return lowestCommonAncestor(root.left, p, q);
        else if(cur < min)
            return lowestCommonAncestor(root.right, p, q);
        else return root;//要把可能性最小的放在最后
    }

    //看看这个第一个版本, 15, 77, 只是进行了一点点取值和判断的优化, 就快了很多(其实只是从9ms变成6ms);
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        int max = Math.max(p.val, q.val);
        int min = Math.min(p.val, q.val);
        if(root.val >= min && root.val <= max){
            return root;
        }else if(root.val > max){
            return lowestCommonAncestor(root.left, p, q);
        }else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}